package io.tec.cloud.algorithm.c10_v20220722;

import java.util.HashSet;
import java.util.Set;

/**
 * 58：58	10_1	10	1	10二叉树常见面试题（上）	两个可能有环的单链表相交的第一个节点
 */
public class Code10_1_FindFirstIntersectNode {

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

    }

    public static Node getIntersectNode(Node head1, Node head2) {
        Node n1 = getLoopNode(head1);
        Node n2 = getLoopNode(head2);


        // 1、都是无环链表
        if (n1 == null && n2 == null) {
            return boothNoLoop(head1, n1, head2, n2);
        }

        // 3、两个都有环
        if (n1 != null && n2 != null) {
            return boothLoop(head1, n1, head2, n2);
        }
        return null;
    }

    private static Node boothLoop(Node head1, Node n1, Node head2, Node n2) {
        int size1 = size(head1, n1);
        int size2 = size(head2, n2);
        // 入环节点相同
        if (n1 == n2) {
            Node longList = head1;
            Node shortList = head2;
            int diffSize = size1 - size2;
            if (diffSize < 0) {
                longList = head2;
                shortList = head1;
            }
            diffSize = Math.abs(diffSize);
            Node c1 = longList;
            Node c2 = shortList;
            while (diffSize > 0 && c1 != null) {
                diffSize--;
                c1 = c1.next;
            }
            while (c1 != c2) {
                c1 = c1.next;
                c2 = c2.next;
            }
            return c1;
        } else {
            Node pivot  = n1;
            // 入环节点不同
            do {
                n1 = n1.next;
                if (n1 == n2) {
                    return pivot;
                }
            } while (n1 != pivot);
        }
        return null;
    }

    private static Node boothNoLoop(Node head1, Node n1, Node head2, Node n2) {
        int size1 = size(head1, n1);
        int size2 = size(head2, n2);
            Node longList = head1;
            Node shortList = head2;
            int diffSize = size1 - size2;
            if (diffSize < 0) {
                longList = head2;
                shortList = head1;
            }
            diffSize = Math.abs(diffSize);
            Node c1 = longList;
            Node c2 = shortList;
            while (diffSize > 0 && c1 != null) {
                diffSize--;
                c1 = c1.next;
            }
            while (c1 != null) {
                if (c1 == c2) {
                    return c1;
                }
                c1 = c1.next;
                c2 = c2.next;
            }
        return null;
    }


    public static Node getIntersectNode2(Node head1, Node head2) {
        Node n1 = getLoopNode(head1);
        Node n2 = getLoopNode(head2);

        return getFirstXNode(head1, n1, head2, n2);
    }

    /**
     * @param head1
     * @param n1
     * @param head2
     * @param n2
     * @return
     */
    private static Node getFirstXNode(Node head1, Node n1, Node head2, Node n2) {
        int size1 = size(head1, n1);
        int size2 = size(head2, n2);
        // 讨论：
        // 1、都是无环链表
        if (n1 == null && n2 == null) {
            Node longList = head1;
            Node shortList = head2;
            int diffSize = size1 - size2;
            if (diffSize < 0) {
                longList = head2;
                shortList = head1;
            }
            diffSize = Math.abs(diffSize);
            Node c1 = longList;
            Node c2 = shortList;
            while (diffSize > 0 && c1 != null) {
                diffSize--;
                c1 = c1.next;
            }
            while (c1 != null) {
                if (c1 == c2) {
                    return c1;
                }
                c1 = c1.next;
                c2 = c2.next;
            }
            return null;
        }

        // 2、一个有环，一个无环
        if ((n1 == null && n2 != null) || (n1 != null && n2 == null)) {
            return null;
        }


        // 3、两个都有环
        if (n1 != null && n2 != null) {
            // 入环节点相同
            if (n1 == n2) {
                Node longList = head1;
                Node shortList = head2;
                int diffSize = size1 - size2;
                if (diffSize < 0) {
                    longList = head2;
                    shortList = head1;
                }
                diffSize = Math.abs(diffSize);
                Node c1 = longList;
                Node c2 = shortList;
                while (diffSize > 0 && c1 != null) {
                    diffSize--;
                    c1 = c1.next;
                }
                while (c1 != c2) {
                    c1 = c1.next;
                    c2 = c2.next;
                }
                return c1;
            } else {
                Node pivot  = n1;
                // 入环节点不同
                do {
                    n1 = n1.next;
                    if (n1 == n2) {
                        return pivot;
                    }
                } while (n1 != pivot);
            }
            return null;
        }
        // 不相交
        return null;
    }

    public static int size(Node head, Node loopNode) {
        if (head == null) {
            return 0;
        }

        Node cur = head;
        int size = 0;
        // TODO 判断环外的长度，需要传参：入环节点，否则进入死循环
        while (cur != null && loopNode != cur) {
            size++;
            cur = cur.next;
        }
        return size;
    }

    /**
     * 是否有环？有则返回入环节点；否则返回null
     *
     * @param head
     * @return
     */
    public static Node getLoopNode(Node head) {

        if (head == null) {
            return null;
        }

        Set<Node> path = new HashSet<>();
        Node cur = head;

        while (cur != null) {
            if (!path.contains(cur)) {
                path.add(cur);
            } else {
                return cur;
            }
            cur = cur.next;
        }

        return null;
    }


    static class Node<V> {
        V value;
        Node next;

        Node(V value) {
            this.value = value;
        }
    }
}
